1. Field of the Invention
The present invention relates to route selecting methods and apparatus and more particularly to a method and an apparatus for selecting the most suitable route between two arbitrary points on map data.
2. Description of the Background Art
As conventionally known, a car navigation system is a system for detecting and displaying a present point of a vehicle, automatically selecting for the most suitable route to a destination, and guiding the vehicle to the destination along the most suitable route by display guidance and/or audio guidance. In the car navigation system, a practical route which the vehicle can always pass through is required to guide the vehicle along the route. Therefore, route searching methods in which regulation information such as one-way traffic regulation and no-right/left-turn regulation is reflected have been considerably studied and suggested.
Conventionally, vehicle route guiding apparatus for selecting a route compliant with the traffic regulation using the steady regulation information as in the above include the one disclosed in Japanese Patent Laying-Open No. 62-82316, for example. In this document, the following method is shown as a method for reflecting the steady regulation information.
FIG. 21 is a diagram showing the structure of the conventional vehicle route guiding apparatus. In FIG. 21, the vehicle route guiding apparatus is composed of basic information storage means 22a for storing map data in which the next reachable adjacent intersection and a required time correlation amount for each intersection are written, considering traffic direction regulation such as do-not-enter and no-right/left-turn, and route searching means 22b for searching the minimum route from a starting intersection to a destination intersection under a certain condition referring to the map data which the basic information storage means 22a stores.
The above conventional method is characterized by a method of representing a road network of the map data recorded in the basic information storage means 22a. Only roads to the reachable intersections are stored in consideration of the traffic regulation, thereby allowing a search for a route compliant with the regulation without requiring a complicated processing by the route searching method 22b.
Here, described is an example of a representation of a road network of the conventional art. FIGS. 22(a) and 22(b) show an example of a representation of the road network (no-right/left-turn regulation). FIG. 22(a) shows an example of an intersection, and its road network is represented as in FIG. 22(b) when the no-right-turn regulation exists in each entering direction of the intersection in the above intersection. That is, a node is assumed for each entering direction of the intersection, and it is assumed that links exit only in passable straight-ahead/left-turn directions.
In this way, the conventional vehicle route guiding apparatus records the map data, using the road network on which the regulation information is reflected, to select a route which reflects the steady traffic regulation by applying the ordinary route search processing.
By the way, in the above-discussed conventional art, only the intersection traffic regulation in one intersection (right/left-turn regulation, for example) is an object to be represented. However, there exist complicated traffic regulations which cannot be represented only by the traffic regulation in one intersection. FIG. 23 shows an example of traffic regulation over a plurality of intersections which cannot be described by the conventional method (hereinafter referred to as composite intersection traffic regulation). In FIG. 23, it is presumed that only A.fwdarw.B and B.rarw.A are prohibited to be passed, and all of the others can be passed. FIG. 24 shows an example of representation of the composite intersection traffic regulation in FIG. 23 using the ordinary intersection traffic regulation on a general network. FIG. 24 represents the road network in FIG. 23 with two nodes (N1 and N2) and five links (L1 to L5). When the intersection traffic regulation shown as in FIG. 24 is applied, a passable route such as L1.fwdarw.N1.fwdarw.L2.fwdarw.N2.fwdarw.L5, for example, is disadvantageously not passable.
Therefore, in order to represent the above composite intersection traffic regulation, a method for unifying a plurality of intersections into one node (unified intersection method) is disclosed in Japanese Patent Laying-Open No. 8-75491. FIG. 25 shows an example of a unified intersection. Here, a node N1 and a node N2 are unified to be a new node NX1. The ordinary traffic regulation (no-straight-ahead regulation to L4.fwdarw.L5 and L5.fwdarw.L4) is written on the node NX1, thereby allowing representation of the regulation contents in FIG. 23.
When the conventional unified intersection method is used, in addition to the ordinary search processing, it is required to refer to cost information (time and distance) for passing through the unified intersection and route information in the unified intersection at the time of route display, thereby disadvantageously resulting in a complicated processing. Furthermore, when the cost in the unified intersection becomes large, the selected route is not necessarily the minimum cost route.
Here, described is an example of cases where the selected route is not the minimum cost route when the unified intersection method is used, using drawings. FIG. 26 is a diagram showing an example of a road network in a case where the selected route is not the minimum cost route when the conventional unified intersection method is used. FIG. 27 is a diagram representing the road network in FIG. 26 with the conventional unified intersection method. In FIG. 26, assume that the minimum cost route from a starting direction to a node N4 is L1.fwdarw.N1.fwdarw.L4.fwdarw.N3.fwdarw.L7.fwdarw.N4 and the minimum cost route to a node N5 is L1.fwdarw.N1.fwdarw.L2.fwdarw.N2.fwdarw.L5.fwdarw.N5. In this case, the minimum cost route from the starting direction to the destination direction is L1.fwdarw.N1.fwdarw.L2.fwdarw.N2.fwdarw.L5.fwdarw.N5.fwdarw.L9. However, when the nodes N4 and N5 are unified in this road network into a unified node NX1 as shown in FIG. 27, the minimum cost route from the starting direction to the unified node NX1 is L1.fwdarw.N1.fwdarw.L4.fwdarw.N3.fwdarw.L7.fwdarw.NX1. Since searches expanse further on the basis of the results, the finally obtained route from the starting direction to the destination direction is L1.fwdarw.N1.fwdarw.L4.fwdarw.N3.fwdarw.L7.fwdarw.NX1.fwdarw.L9, which is different from the correct minimum cost route as shown in FIG. 26.